#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

bool search(vector<int>& nums, int target) {
    int n = nums.size();
    int l = -1, r = n - 1;
    auto check = [&](int mid)->bool {
        if (nums[mid] > nums[r])
            return target > nums[r] && nums[mid] >= target;
        return target > nums[r] || nums[mid] >= target;
    };
    while (l + 1 < r)
    {
        int mid = l + (r - l) / 2;
        if (nums[mid] == nums[r])    r--;
        else if (check(mid)) r = mid;
        else l = mid;
    }
    return nums[r] == target;
}